package classics.DP;

/**
 * ex5 最长回文字串
 * 动态规划解决方法
 */
public class Ex5 {
    public static String longestPalindrome(String s) {
        if(s.length()==1){
            return s;
        }
        boolean[][] dp = new boolean[s.length()][s.length()];
        int max = 0;
        String res = s.substring(0,1);
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        for (int i = 2; i <= s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                int l = j;
                int r = j+i-1;
                if(r>=s.length()){
                    continue;
                }
                if((l+1>r-1||dp[l+1][r-1]==true)&&s.charAt(l)==s.charAt(r)){
                    dp[l][r]=true;
                    if(i>max){
                        max = i;
                        res = s.substring(l,r+1);
                    }
                }else{
                    dp[l][r]=false;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(Ex5.longestPalindrome("aa"));
    }
}
